// 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。

// 执行用时：
// 20 ms
// , 在所有 C++ 提交中击败了
// 71.08%
// 的用户
// 内存消耗：
// 25.3 MB
// , 在所有 C++ 提交中击败了
// 77.43%
// 的用户

// 看了题解，待优化，find函数，可以通过map

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_map>
#include<set>
#include<queue>
using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
 
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* res =tra(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);
        return res;
    }

    TreeNode* tra(vector<int>& preorder, vector<int>& inorder,int pl,int pr,int il,int ir){
        if(pl>pr || il>ir){
            return NULL;
        }
        if(pr>preorder.size()-1 || ir > inorder.size()-1){
            return NULL;
        }
        TreeNode* root = new TreeNode(preorder[pl]);
        auto it = find(inorder.begin()+il,inorder.begin()+ir+1,preorder[pl]);
        int index = it - inorder.begin();
        int distance = index - il;
        root->left = tra(preorder,inorder,pl+1,pl+distance,il,index-1);
        root->right = tra(preorder,inorder,pl+1+distance,pr,index+1,ir);
        return root;
    }
};